package mess;

public class LeeCode_45 {
    public static void main(String[] args) {
        int[] nums = new int[]{5,9,3,2,1,0,2,3,3,1,0,0};
        System.out.println(jump(nums));
    }
    private static int jump(int[] nums) {
        int len = nums.length;

        int index = 0;
        int count = 0;
        int distance = len - 1 - index;
        while (distance > 0){
            if (nums[index] >= distance){
                count++;
                break;
            }
            int max = 0;
            int maxIndex = 0;
            int step = nums[index];
            for (int i = 1; i <= step; i++) {
                if (i + nums[i + index] > max){
                    max = i + nums[i + index];
                    maxIndex = index + i;
                }
            }
            index = maxIndex;
            count++;
            distance = len - 1 - index;
        }
        return count;
    }
}
